package deque;

import java.util.*;

public class LinkedListDeque<T> implements Iterable<T>, Deque<T> {
    private static class Node<T> {
        T value;
        Node<T> next;

        Node(T value) {
            this.value = value;
            this.next = null;
        }
    }


    private Node<T> first;
    private Node<T> last;
    private int size;

    public LinkedListDeque() {
        first = null;
        last = null;
        size = 0;
    }

    public void addFirst(T item) {
        Node<T> node1 = new Node(item);
        Node<T> temp;
        this.size += 1;
        if (first == null) {
            first = node1;
            last = node1;
        }
        temp = this.first;
        this.first = node1;
        node1.next = temp;
    }

    public void addLast(T item) {
        Node<T> node1 = new Node<>(item);
        if (this.first == null) {
            this.first = node1;
            this.last = node1;
            first.next = null;
            size++;
            return;
        } else {
            this.last.next = node1;
            this.last = node1;
            last.next = null;
            this.size++;
        }
    }


    public int size() {
        return this.size;
    }

    public void printDeque() {
        Node<T> node1 = first;
        while (node1 != null) {
            System.out.print(first.value + " ");
            node1 = node1.next;
        }
    }

    public T removeFirst() {
        Node<T> node2;
        if (first == null) {
            return null;
        } else if (first == last) {
            this.size = this.size - 1;
            node2 = first;
            first = null;
            last = null;
            return (T) node2.value;
        } else {
            node2 = first;
            first = first.next;
            this.size = this.size - 1;
            return (T) node2.value;
        }
    }

    public T removeLast() {
        Node<T> node1 = first;
        Node<T> node2;
        if (first == null) {
            return null;
        } else if (first == last) {
            this.size -= 1;
            first = null;
            node2 = last;
            last = null;
            return (T) node2.value;
        } else {
            while (node1.next.next != null) {
                node1 = node1.next;
            }
            node2 = node1.next;
            last = node1;
            last.next = null;
            this.size = this.size - 1;
            return (T) node2.value;
        }
    }

    public T get(int index) {
        Node<T> node1 = first;
        for (int i = 0; i < size; i++) {
            if (i == index) {
                return node1.value;
            }
            node1 = node1.next;
        }
        return null;
    }

    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private Node<T> current = first;  // 从第一个节点开始遍历

            @Override
            public boolean hasNext() {
                return current != null;  // 如果当前节点不为空，表示还有下一个节点
            }

            @Override
            public T next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();  // 如果没有更多元素，抛出异常
                }
                T value = current.value;  // 获取当前节点的值
                current = current.next;  // 将当前节点移动到下一个节点
                return value;  // 返回当前节点的值
            }
        };
    }

    @Override
    public boolean equals(Object o) {
        // 1. 检查是否与自身比较
        if (this == o) {
            return true;
        }

        // 2. 检查传入对象是否为null或类型是否匹配
        if (o == null || getClass() != o.getClass()) {
            return false;
        }

        // 3. 将对象强制转换为LinkedListDeque
        LinkedListDeque<?> other = (LinkedListDeque<?>) o;

        // 4. 比较两个链表的大小
        if (this.size != other.size) {
            return false;
        }

        // 5. 遍历两个链表，逐个比较每个节点的值
        Node<T> currentThis = this.first;
        Node<?> currentOther = other.first;

        while (currentThis != null && currentOther != null) {
            if (!Objects.equals(currentThis.value, currentOther.value)) {
                return false;  // 如果有一个节点的值不同，返回false
            }
            currentThis = currentThis.next;
            currentOther = currentOther.next;
        }

        // 6. 如果所有节点的值都相等，返回true
        return true;
    }


    public T getRecursive(int index) {
        return getRecursiveHelper(first, index);
    }

    private T getRecursiveHelper(Node current, int index) {
        if (index == 0) {
            return (T) current.value;
        }
        return (T) getRecursiveHelper(current.next, index - 1);
    }
}


